package _dp_base;

import java.util.Arrays;

/**
 * 91. 解码方法
 */
public class No91 {
    private String s;
    private int[] cache;

    public int numDecodings(String s) {
        this.s = s;
        int n = s.length();
        cache = new int[n];
        Arrays.fill(cache, -1);

        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) return 1;
        else if (cache[i] != -1) return cache[i];
        // 仅剩一个字符的情况
        char c = s.charAt(i);
        if (i == 0) return c == '0' ? 0 : 1;
        // 剩两个字符及以上的情况
        int judge = (s.charAt(i - 1) - '0') * 10 + (c - '0');
        if (c == '0') return (judge == 10 || judge == 20) ? cache[i] = dfs(i - 2) : 0;
        else if (judge < 10 || judge > 26) return cache[i] = dfs(i - 1);
        else return cache[i] = dfs(i - 1) + dfs(i - 2);
    }
}
